package com.lft.sort06.merge_sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] a = {8, 4, 5, 7, 1, 3, 6, 2, -1, 9, 10, -3};
		// 归并排序需要一个额外的空间。
		int[] temp = new int[a.length];
		int[] as = mergeSort(a, 0, a.length - 1, temp);
		System.out.println(Arrays.toString(as));
		
	}
	
	/**
	 * 拆分的方法。递归拆分完之后，依次合并。
	 * @param a     排序的原始数组
	 * @param left  左边起始索引
	 * @param right 右边边界索引
	 * @param temp  中转数组
	 * @return int[] 拆分合并排序之后的数组。
	 */
	public static int[] mergeSort(int[] a, int left, int right, int[] temp) {
		if (left < right) {
			int mid = (left + right) / 2;
			// 向左递归进行分解
			mergeSort(a, left, mid, temp);
			// 向右递归进行分解
			mergeSort(a, mid + 1, right, temp);
			// 合并
			merge(a, left, mid, right, temp);
		}
		return a;
	}
	
	/**
	 * 合并的方法
	 * @param a     排序的原始数组
	 * @param left  左边有序序列的初始索引
	 * @param mid   中间索引
	 * @param right 右边索引
	 * @param temp  中转数组
	 * @return 合并排序好的有序序列
	 */
	public static int[] merge(int[] a, int left, int mid, int right, int[] temp) {
		// 初始化 l 左边有序序列的初始索引
		int l = left;
		// 初始化 r 右边有序序列的初始索引
		int r = mid + 1;
		// 初始化 指向 temp 数组的索引
		int tempIndex = 0;
		// 1. 先把左右两边（有序）的数据按照规则填充到 temp 数组
		// 直到左右两边的有序序列，有一边处理完成为止。
		while (l <= mid && r <= right) {
			// 如果左边的小于等于右边的，将左边的复制到 temp[tempIndex]上。然后 左边右移一位，tempIndex 也右移一位。
			if (a[l] <= a[r]) {
				temp[tempIndex] = a[l];
				tempIndex++;
				l++;
			}
			// 如果右边的大于左边的，将右边的复制到 temp[tempIndex]上。然后 右边右移一位，tempIndex 也右移一位。
			else {
				temp[tempIndex] = a[r];
				tempIndex++;
				r++;
			}
		}
		
		// 2. 交另外一边的依次复制到 temp 数组中。
		// 左边没有复制完。
		while (l <= mid) {
			temp[tempIndex] = a[l];
			tempIndex++;
			l++;
		}
		// 右边没有复制完。
		while (r <= right) {
			temp[tempIndex] = a[r];
			tempIndex++;
			r++;
		}
		
		// 3. 再将 temp 数组复制给原始数组。注意：每次都拷贝所有的。
		tempIndex = 0;
		int tempLeft = left;
		// System.out.println("tempLeft: " + tempLeft + "  right: " + right);
		while (tempLeft <= right) {
			a[tempLeft] = temp[tempIndex];
			tempIndex++;
			tempLeft++;
		}
		return a;
	}
}
